package 图;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

public class Knight {
	private static Node[][] arr;
	private static int[][] directs = new int[][] { { 1, 2 }, { 2, 1 }, { -1, 2 }, { 1, -2 }, { -1, -2 }, { -2, 1 },
			{ 2, -1 }, { -2, -1 } };

	public static void main(String[] args) {
		arr = new Node[8][8];
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				arr[i][j] = new Node(i, j);
			}
		}
		/*int result = 0;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				result += knight(i, j);
			}
		}
		System.out.println(result);*/
		System.out.println(knight(4, 5));

	}

	public static int knight(int x, int y) {
		Stack<Node> stack = new Stack<>();
		Set<Node> set = new HashSet<>();
		stack.push(arr[x][y]);
		int result = 0;
		int depth;
		while (!stack.isEmpty()) {
			if (stack.size() == 64) {
				result++;
			} 

			Node node = stack.pop();
			set.remove(node);
			for (int i = 0; i < directs.length; i++) {
				Node next = new Node(node.x + directs[i][0], node.y + directs[i][1]);
				if (next.x < 0 || next.x >= arr.length || next.y < 0 || next.y >= arr.length || set.contains(next)) {
					continue;
				}
				stack.push(node);
				stack.push(next);
				set.add(node);
				set.add(next);
				
				System.out.println(next);
				break;
			}
		}
		return result;
	}

	private static class Node {
		int x, y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public boolean equals(Object obj) {
			Node node = (Node) obj;
			return x == node.x && y == node.y;
		}
		
		@Override
		public int hashCode() {
			return x * 31 + y;
		}

		@Override
		public String toString() {
			return "Node [x=" + x + ", y=" + y + "]";
		}

	}
}
